COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	exerci.lsp[s86,jmc]	LISP exercise computing probabilities
C00005 ENDMK
C⊗;
exerci.lsp[s86,jmc]	LISP exercise computing probabilities

Let  n  cards be chosen from the usual deck of 52. (prob k n)
is the probability that they are of  k  different denominations.
The LISP recursive program for this function illustrates nicely
the virtues of LISP for writing kind
It is more straightforward to write a recursive LISP program for this
than to write it in Pascal or other algolic language, because
one intermediate data structure required is a list of numbers
of variable length.  For example, if 5 cards are chosen, then
(3 1 1) represents 3 cards of one denomination and 1 each of
two other denominations.  The recursive computation requires
computing the probabilities of these configurations.

However, the recursive program will not be fully efficient, because
it will recompute the probability of a configuration each
time it is required by a recursive call.  Some form of memoization
is needed so that the probabilities will be remembered.  LISP
needs a systematic way of calling for this.

It would be interesting to see how this would go in Prolog.

We could vary the structure of the deck, i.e. vary the four suits of
13 cards, but it seems unlikely that this would be instructive, so
we won't.

Let  u  denote a configuration as above.  We have

(defun prob (u)
       (if (equal u '(1))
	   1.0
	   (do ((v (preds u) (cdr v))
		(s 0.0 (plus s (times (prob (car v)) (prob1 (car v) u)))))
	       ((null v) s))))

(defun preds (u)
       (maplis #'(lambda (w)
			 (fix (maplis #'(lambda (w1)
						(if (eq w1 w)
						    (sub1 (car w1))
						    (car w1))) u))) u))

(defun fix (w)


Hmm. Maybe we should change the representation of configuration to be
have the form (<number of cards of denomination k> <number of cards
present in that number>)*.  Here  *  is the Kleene star denoting a
list.